The present invention relates to a priority encoder and a priority encoding method, and more particularly to a priority encoder capable of encoding input signals into addresses for sequential outputs of the encoded addresses in accordance with predetermined priorities, wherein the priority encoder encodes correspondence signals from memory cells of an associative memory.
It is necessary for the normal memory to designate its address for reading out data from the designated address or writing data into the designated address. By contrast to the normal memory, the associative memory or a content addressable memory has not only the same function of random access memory but also additional functions of providing informations about existences of data identical with or similar to entered retrieval data as well as about other data on one or more words having identical or similar data and those addresses. If a word includes data identical with or similar to entered retrieval data, then it is referred to as the word corresponds to the entered retrieval data. It is possible that a plurality of words corresponds to the entered retrieval data. If the plural word correspond to the entered retrieval data, then the function possessed by the normal encoder is incapable of correct outputs. The content addressable memory is responsible to the case where the plural word correspond to the entered retrieval data. Namely, the content addressable memory has a priority encoder which is capable of encoding correspondence signals for sequential outputs of address signals in accordance with predetermined priorities, wherein the correspondence signal means that a correspondence with the entered retrieval data.
A conventional priority encoder is disclosed in Japanese laid-open patent publication No. 5-189979. This conventional priority encoder will be described with reference to FIG. 1 which is a circuit diagram illustrative of the conventional priority encoder provided in the content addressable memory.
The conventional priority encoder has a hierarchical structure of three hierarchies, for example, the uppermost level, intermediate level and the lowermost level. The lowermost level hierarchy has sixteen first level hierarchy priority circuits 11-0, 11-1, 11-2, - - - 11-15. Each of the sixteen first level hierarchy priority circuits 11-0, 11-1, 11-2, - - - 11-15 is connected to a first level address encoder 14 so that the first level address encoder 14 receives output signals from the first level hierarchy priority circuit for encoding the output signals into address signals of two bits. The intermediate level hierarchy has four second level hierarchy priority circuits 12-0, 12-1, 12-2, and 12-3. Each of the four second level hierarchy priority circuits 12-0, 12-1, 12-2, and 12-3 is connected to a second level address encoder 14 so that tie second level address encoder 14 receives output signals from the second level hierarchy priority circuit for encoding the output signals into address signals of two bits. The uppermost level hierarchy has a single third level hierarchy priority circuit 13. The single third level hierarchy priority circuit 13 is connected to a third level address encoder 14 so that the third level address encoder 14 receives output signals from the third level hierarchy priority circuit for encoding the output signals into address signals of two bits.
Each of the sixteen first level hierarchy priority circuits 11-0, 11-1, 11-2, - - - 11-15 and the four second level hierarchy priority circuits 12-0, 12-1, 12-2, and 12-3 has a single OR-output terminal "OR" from which OR-output signal is outputted. Each of the sixteen first level hierarchy priority circuits 11-0, 11-1, 11-2, - - - 11-15 and the four second level hierarchy priority circuits 12-0, 12-1, 12-2, and 12-3 as well as the single third level hierarchy priority circuit 13 has four input terminals. The four input terminals of the second level hierarchy priority circuit 12-0 are connected to the OR-output terminals "OR" of the four first level hierarchy priority circuits 11-0, 11 -2 and 11-3 respectively The four input terminals of the second level hierarchy priority circuit 12-1 are connected to the OR-output terminals "OR" of the four first level hierarchy priority circuits 11-4, 11-5, 11-6 and 11-7 respectively. The four input terminals of the second level hierarchy priority circuit 12-2 are connected to the OR-output terminals "OR" of the four first level hierarchy priority circuits 11-8, 11-9, 11-10 and 11-11 respectively. The four input terminals of the second level hierarchy priority circuit 12-3 are connected to the OR-output terminals "OR" of the four first level hierarchy priority circuits 11-12, 11-13, 11-14 and 11-15 respectively. The four input terminals of the third level hierarchy priority circuit 13 are connected to the OR-output terminals "OR" of the four second level hierarchy priority circuits 12-0, 12-1, 12-2 and 12-3 respectively. The four input terminals of each of the first level hierarchy priority circuits 11-0, 11-1, 11-2, - - - 11-15 receive correspondence signals in binary digits, wherein high level "1" means the correspondence with the entered retrieval signal, whilst the low level "0" means no correspondence with the entered retrieval signal. The OR-output signal becomes high level "1" when at least any one of the input signals as the correspondence signals is high level "1". Otherwise, the OR-output signal becomes low level "0".
Each of the sixteen first level hierarchy priority circuits 11-0, 11-1, 11-2, - - - 11-15 and the four second level hierarchy priority circuits 12-0, 12-1, 12-2, and 12-3 also has a single enable input terminal "EN". The enable input terminal "EN" is provided in a first side of the priority circuit, whilst the OR-output terminal "OR" is provided in a second side of the priority circuit, wherein the first side corresponds to the upper side whilst the second side corresponds to the lower side. In the four input terminals of the individual priority circuit, the nearest terminal to the upper side of the individual priority circuit is the uppermost input terminal. In the four input terminals of the individual priority circuit, the second nearest terminal to the upper side of the individual priority circuit is the upper input terminal. In the four input terminals of the individual priority circuit, the second nearest terminal to the lower side of the individual priority circuit is the lower input terminal. In the four input terminals of the individual priority circuit, the nearest terminal to the lower side of the individual priority circuit is the lowermost input terminal. The individual priority circuit also has four output terminals. In the four input terminals of the individual priority circuit, the nearest terminal to the upper side of the individual priority circuit is the uppermost output terminal In the four input terminals of the individual priority circuit, the second nearest terminal to the upper side of the individual priority circuit is the upper output terminal. In the four input terminals of the individual priority circuit, the second nearest terminal to the lower side of the individual priority circuit is the lower output terminal. In the four input terminals of the individual priority circuit, the nearest terminal to the lower side of the individual priority circuit is the lowermost output terminal. An uppermost output signal from the uppermost output terminal is the first appearance. An upper output signal from the upper output terminal is the second appearance. A lower output signal from the lower output terminal is the third appearance. A lowermost output signal from the lowermost output terminal is the fourth appearance. Namely, in the individual priority circuit, the four output signals are outputted in the order of uppermost to lowermost output signals.
Namely, the lowermost level hierarchy has the first level hierarchy uppermost priority circuit 11-0, the first level hierarchy second upper priority circuit 11-1, the first level hierarchy third upper priority circuit 11-2, the first level hierarchy fourth upper priority circuit 11-3, the first level hierarchy fifth upper priority circuit 11-4, the first level hierarchy sixth upper priority circuit 11-5, the first level hierarchy seventh upper priority circuit 11-6, the first level hierarchy eighth upper priority circuit 11-7, the first level hierarchy eighth lower priority circuit 11-8, the first level hierarchy seventh lower priority circuit 11-9, the first level hierarchy sixth lower priority circuit 11-10, the first level hierarchy fifth lower priority circuit 11--11, the first level hierarchy fourth lower priority circuit 11-12, the first level hierarchy third lower priority circuit 11-13, the first level hierarchy second lower priority circuit 11-14, and the first level hierarchy lowermost priority circuit 11-15.
Namely, the intermediate level hierarchy has the second level hierarchy uppermost priority circuit 12-0, the second level hierarchy second upper priority circuit 12-1, the second level hierarchy second lower priority circuit 12-2, and the second level hierarchy lowermost priority circuit 12-3. The lowermost level hierarchy has the single third level hierarchy priority circuit 13.
The uppermost output terminal of the second level hierarchy uppermost priority circuit 12-0 is connected to the enable input terminal "EN" of the first level hierarchy uppermost priority circuit 11-0, so that the output signal is fed back to the enable input terminal "EN". The upper output terminal of the second level hierarchy uppermost priority circuit 12-0 is connected to the enable input terminal "EN" of the first level hierarchy second upper priority circuit 11-1, so that the output signal is fed back to the enable input terminal "EN". The lower output terminal of the second level hierarchy uppermost priority circuit 12-0 is connected to the enable input terminal "EN" of the first level hierarchy third upper priority circuit 11-2, so that the output signal is fed back to the enable input terminal "EN". The lowermost output terminal of the second level hierarchy uppermost priority circuit 12-0 is connected to the enable input terminal "EN" of the first level hierarchy fourth upper priority circuit 11-3, so that the output signal is fed back to the enable input terminal "EN".
The uppermost output terminal of the second level hierarchy second upper priority circuit 12-1 is connected to the enable input terminal "EN" of the first level hierarchy fifth upper priority circuit 11-4, so that the output signal is fed back to the enable input terminal "EN". The upper output terminal of the second level hierarchy second upper priority circuit 12-1 is connected to the enable input terminal "EN" of the first level hierarchy sixth upper priority circuit 11-5, so that the output signal is fed back to the enable input terminal "EN". The lower output terminal of the second level hierarchy second upper priority circuit 12-1 is connected to the enable input terminal "EN" of the first level hierarchy seventh upper priority circuit 11-6, so that the output signal is fed back to the enable input terminal "EN". The lowermost output terminal of the second level hierarchy second upper priority circuit 12-1 is connected to the enable input terminal "EN" of the first level hierarchy eighth upper priority circuit 11-7, so that the output signal is fed back to the enable input terminal "EN".
The uppermost output terminal of the second level hierarchy second lower priority circuit 12-2 is connected to the enable input terminal "EN" of the first level hierarchy eighth lower priority circuit 11-8, so that the output signal is fed back to the enable input terminal "EN". The upper output terminal of the second level hierarchy second lower priority circuit 12-2 is connected to the enable input terminal "EN" of the first level hierarchy seventh lower priority circuit 11-9, so that the output signal is fed back to the enable input terminal "EN". The lower output terminal of the second level hierarchy second lower priority circuit 12-2 is connected to the enable input terminal "EN" of the first level hierarchy sixth lower priority circuit 11-10, so that the output signal is fed back to the enable input terminal "EN". The lowermost output terminal of the second level hierarchy second lower priority circuit 12-2 is connected to the enable input terminal "EN" of the first level hierarchy fifth lower priority circuit 11--11, so that the output signal is fed back to the enable input terminal "EN".
The uppermost output terminal of the second level hierarchy lowermost priority circuit 12-3 is connected to the enable input terminal "EN" of the first level hierarchy fourth lower priority circuit 11-12, so that the output signal is fed back to the enable input terminal "EN". The upper output terminal of the second level hierarchy lowermost priority circuit 12-3 is connected to the enable input terminal "EN" of the first level hierarchy third lower priority circuit 11-13, so that the output signal is fed back to the enable input terminal "EN". The lower output terminal of the second level hierarchy lowermost priority circuit 12-3 is connected to the enable input terminal "EN" of the first level hierarchy second lower priority circuit 11-14, so that the output signal is fed back to the enable input terminal "EN". The lowermost output terminal of the second level hierarchy lowermost priority circuit 12-3 is connected to the enable input terminal "EN" of the first level hierarchy lowermost priority circuit 11-15, so that the output signal is fed back to the enable input terminal "EN".
The uppermost output terminal of the third level hierarchy priority circuit 13 is connected to the enable input terminal "EN" of the second level hierarchy uppermost priority circuit 12-0, so that the output signal is fed back to the enable input terminal "EN". The upper output terminal of the third level hierarchy priority circuit 13 is connected to the enable input terminal "EN" of the second level hierarchy second upper priority circuit 12-1, so that the output signal is fed back to the enable input terminal "EN". The lower output terminal of the third level hierarchy priority circuit 13 is connected to the enable input terminal "EN" of the second level hierarchy second lower priority circuit 12-2, so that the output signal is fed back to the enable input terminal "EN". The lowermost output terminal of the third level hierarchy priority circuit 13 is connected to the enable input terminal "EN" of the second level hierarchy lowermost priority circuit 12-3, so that the output signal is fed back to the enable input terminal "EN".
As described above, the conventional priority encoder circuit of FIG. 1 has the sixteen lowermost level hierarchy priority circuits 11-0 to 11-15, each having the four input terminals, so that the conventional priority encoder circuit of FIG. 1 has 64 input terminals for receiving 64 input signals. Namely, the conventional priority encoder circuit of FIG. 1 encodes 64 input signals to output encoded address signals of 6-bits (A0, A1, A2, A3, A4 and A5).
All of the address encoders 14 has the same circuit configuration which has a set of four MOS field effect transistors 15. Gates of two of the MOS field effect transistors 15 are connected to the uppermost output terminal of the individual priority circuit. A gate of the other MOS filed effect transistor 15 is connected to the upper output terminal of the individual priority circuit. A gate of the remaining MOS filed effect transistor 15 is connected to the lower output terminal of the individual priority circuit. The lowermost output terminal of the individual priority circuit is not connected to the address encoder. The individual MOS filed effect transistors 15 perform ON/OFF operations in accordance with the output signal from the address encoder. As described above, the address signals encoded by the priority encoder are 6-bits (A0, A1, A2, A3, A4 and A5). The sixteen address encoders 14 connected to the output terminals of the sixteen lowermost level hierarchy priority circuits 11-0 to 11-15 are operated to decide the lowermost bit A0 and the second lower bit A1 of the 6-bits address signals. The four address encoders 14 connected to the output terminals of the four intermediate level hierarchy priority circuits 12-0 to 12-3 are operated to decide the third lower bit A2 and the third upper bit A3 of the 6-bits address signals. The single address encoder 14 connected to the output terminals of the single uppermost level hierarchy priority circuit 13 is operated to decide the second upper bit A4 and the uppermost bit A5 of the 6-bits address signals.
Each of the sixteen uppermost level hierarchy priority circuits 11-0, 11-1, 11-2, - - - 11-15 and the four intermediate level hierarchy priority circuits 12-0, 12-1, 12-2, and 12-3 as well as the lowermost level hierarchy priority circuit 13 is operated to output the high level output signal "1" from the uppermost output terminal only.
As described above, output signals from the uppermost level hierarchy priority circuit 13 are fed back to the enable input signal terminals of the four intermediate level hierarchy priority circuits 12-0, 12-1, 12-2, and 12-3 and also output signals from the four intermediate level hierarchy priority circuits 12-0, 12-1, 12-2, and 12-3 are also fed back to the enable input signal terminals of the sixteen uppermost level hierarchy priority circuits 11-0, 11-1, 1-12, - - - 11-15, so that of all of the input signals inputted into the sixteen uppermost level hierarchy priority circuits 11-0, 11-1, 11-2, - - - 11-15 are low level "0" indicating no correspondence with the entered retrieval signal, then the output signals from the sixteen uppermost level hierarchy priority circuits 11-0, 11-1, 11-2, - - - 11-15 are made invalid and further the output signals from the four intermediate level hierarchy priority circuits 12-0, 12-1, 12-2, and 12-3 are also made invalid. If a plurality of the correspondence signals "1" are inputted into the priority encoder, then encoded address signals of 6-bits are sequentially outputted into the terminals A0, A1, A2, A3, A4, and A5 in the order of the priorities possessed by the correspondence signal "1" inputted into the priority encoder. For example, an encoded address signal of 6-bits from the correspondence signal "1" having the highest priority is first outputted into the terminals A5, A4, A3, A2, A1, and A0.
As the capacity of the advanced content addressable memory has been on the increase, the number of inputs into the priority encoder has also been on the increase.
The conventional priority encoder has been designed to have the hierarchical structure for realizing high speed performance. This hierarchical structure requires that the outputs of the lower level priority circuit are fed back to the enallc input terminal of the upper level priority circuit, for which reason it takes a long time to output the encoded result.
In the above circumstances, it had been required to develop a novel priority encoder free from the above problems.